<!DOCTYPE html><html class="appearance-light" lang="zh-CN"><head><meta charset="UTF-8"><title>常用代码模板</title><meta name="description" content="如你所见, 希望做个能言善道的人"><meta name="viewport" content="width=device-width, minimum-scale=1.0, maximum-scale=1.0, user-scalable=no, initial-scale=1"><!-- Google Analytics --><!-- End Google Analytics -->
<!-- Baidu Analytics --><!-- End Baidu Analytics --><link rel="icon" href="/images/touxiang.jpg"><link rel="stylesheet" href="/style/common/bulma.css"><link rel="stylesheet" href="/style/base.css"><link rel="stylesheet" href="/style/icon.css"><link rel="stylesheet" href="/style/common/helper.css"><script src="/js/common.js"></script><link rel="stylesheet" href="/style/post.css"><link rel="stylesheet" href="/style/themes/highlight-theme-light.css"><script src="/js/highlight.pack.js"></script><meta name="description" content="收集各种基础算法的通用模板，持续更新中。


模板来自AcWing y总。
排序最常用的排序，快速排序，属于交换类排序。
void qSort(int a[], int l, int r) &amp;#123;
    if (l &amp;gt;= r) return; //递归结束条件 划分到只剩下一个数

    int x = a[l + r &amp;gt;&amp;gt; 1], i = l - 1, j = r + 1; //选定比较数的方法还有很多
    while (i &amp;lt; j) &amp;#123;
        do i++; while (a[i] &amp;lt; x);
        do j++; while (a[j] &amp;gt; x);
        if (i &amp;lt; j) swap(a[i], a[j].."><meta name="generator" content="Hexo 5.4.0"></head><body class="is-flex is-flex-direction-column"><header class="header-widget is-flex-shrink-0 is-hidden-mobile"><div class="container is-fullhd is-flex is-justify-content-space-between is-align-items-center is-full-height"><section class="is-hidden-mobile is-flex-shrink-0"><h2><a href="/">insight's blog</a></h2></section><h3 class="is-hidden-mobile is-family-serif is-full-height is-flex is-align-items-center is-flex-shrink-0"><div class="is-full-height" id="postTopic"><p class="is-full-height is-flex-shrink-0 is-flex is-align-items-center is-justify-content-center">常用代码模板</p><p class="is-full-height is-flex-shrink-0 is-flex is-align-items-center is-justify-content-center">点击返回顶部</p></div></h3><aside class="is-flex-shrink-0"><h3 class="is-inline-block"><a href="/">首页</a></h3><h3 class="is-inline-block"><a href="/about">关于</a></h3><h3 class="is-inline-block"><a href="/archives">归档</a></h3></aside></div></header><header class="is-flex header-widget is-flex-shrink-0 is-align-items-center is-justify-content-center is-hidden-tablet"><h3 class="is-inline-block"><a href="/">首页</a></h3><h3 class="is-inline-block"><a href="/about">关于</a></h3><h3 class="is-inline-block"><a href="/archives">归档</a></h3></header><main><main class="container is-max-widescreen content section post-page pt-4 px-4"><div class="columns is-flex-desktop is-justify-content-center is-flex-direction-row-reverse"><div class="column is-3 is-hidden-mobile"><ol class="toc"><li class="toc-item toc-level-2"><a class="toc-link" href="#%E6%8E%92%E5%BA%8F"><span class="toc-text">排序</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE"><span class="toc-text">二分查找</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E5%A4%A7%E6%95%B0%E5%8A%A0%E5%87%8F%E4%B9%98%E9%99%A4"><span class="toc-text">大数加减乘除</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E5%9B%A0%E6%95%B0%E4%B8%AA%E6%95%B0%E4%B8%8E%E5%9B%A0%E6%95%B0%E4%B9%8B%E5%92%8C"><span class="toc-text">因数个数与因数之和</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#%E5%9B%A0%E6%95%B0%E4%B8%AA%E6%95%B0"><span class="toc-text">因数个数</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E5%9B%A0%E6%95%B0%E4%B9%8B%E5%92%8C"><span class="toc-text">因数之和</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E7%A9%B6%E6%9E%81%E4%BD%8D%E8%BF%90%E7%AE%97%E7%94%A8%E6%B3%95%E6%94%B6%E9%9B%86"><span class="toc-text">究极位运算用法收集</span></a></li></ol></div><div class="column is-9"><header class="my-4"></header><h1 class="mt-0 mb-1 is-family-serif" id="postTitle">常用代码模板</h1><time class="has-text-grey" datetime="2021-06-21T04:22:40.290Z">2021-06-21</time><article class="mt-2 post-content"><p>收集各种基础算法的通用模板，持续更新中。</p>
<span id="more"></span>

<p>模板来自AcWing y总。</p>
<h2 id="排序"><a href="#排序" class="headerlink" title="排序"></a>排序</h2><p>最常用的排序，快速排序，属于交换类排序。</p>
<pre><code class="c++">void qSort(int a[], int l, int r) &#123;
    if (l &gt;= r) return; //递归结束条件 划分到只剩下一个数

    int x = a[l + r &gt;&gt; 1], i = l - 1, j = r + 1; //选定比较数的方法还有很多
    while (i &lt; j) &#123;
        do i++; while (a[i] &lt; x);
        do j++; while (a[j] &gt; x);
        if (i &lt; j) swap(a[i], a[j]);
    &#125;
    qSort(a, l, j), qSort(a, j + 1, r);
&#125;
</code></pre>
<p>快排日常已经够用了，但也有不能满足需要的时候，比如求逆序对，这个时候就要用到归并排序。</p>
<pre><code class="c++">void mergeSort(int a[], int l, int r) &#123;
    if (l &gt;= r) return; //递归结束条件 划分到只剩下一个数
    
    int mid = l + r &gt;&gt; 1;
    mergeSort(a, l, mid);
    mergeSort(a, mid + 1, r);
    int t[N];
    int index = 0, i = l, j = mid + 1;
    //对一分为二的数组 进行比较 然后拷贝到临时数组里面
    while (i &lt;= mid &amp;&amp; j &lt;= r) &#123;    
        if (a[i] &lt; a[j]) t[index++] = a[i++];
        else t[index++] = a[j++];
    &#125;
    //两个数组可能还有剩余 这时直接把剩下的全拷贝过去
    while (i &lt;= mid) t[index++] = a[i++];
    while (j &lt;= r) t[index++] = a[j++];
    //最后拷贝已经有序临时数组 
    for (i = l, j = 0; i &lt;= r; i ++, j ++ ) a[i] = t[j];
&#125;
</code></pre>
<h2 id="二分查找"><a href="#二分查找" class="headerlink" title="二分查找"></a>二分查找</h2><p>要求已有数据为有序状态。<br>$$</p>
<p>$$<br><strong>整数二分和浮点数二分的区别是</strong></p>
<ol>
<li><p><strong>循环结束条件的写法</strong></p>
</li>
<li><p><strong>浮点数不能使用位运算</strong></p>
</li>
</ol>
<pre><code class="c++">//整数
while (l &lt; r) &#123;
     mid = (r - l) &gt;&gt; 1 + l;
&#125;
//浮点数 
//因为浮点数会有精度损失问题 所以使用这样的比较写法
//1e-n 保留 n 位小数 保险起见可以多加一位
while (r - l &lt; 1e-n) &#123;
    mid = (r - l) / 2.0 + l;
&#125;
</code></pre>
<p>划分的区间为 [l, mid]，[mid + 1, r] 时，一般用途求最小化。</p>
<pre><code class="c++">//划分的区间为[l, mid]，[mid + 1, r]
int binarySearch_1(int l, int r) &#123;
    while (l &lt; r) &#123;
        int mid = (r - l) &gt;&gt; 1 + l; //防止溢出 好习惯 从我做起
        if (check(mid)) r = mid;
        else l = mid + 1;
    &#125;
    return l;
&#125;
</code></pre>
<p>划分的区间为 [l, mid - 1]，[mid, r] 时，一般用途求最大化。</p>
<pre><code class="c++">//划分的区间为[l, mid - 1]，[mid, r]
int binarySearch_1(int l, int r) &#123;
    while (l &lt; r) &#123;
        int mid = (r - l + 1) &gt;&gt; 1 + l; //需要额外加1 防止死循环
        if (check(mid)) l = mid;
        else r = mid - 1;
    &#125;
    return l;
&#125;
</code></pre>
<p>如果你对区间的划分和对应的二分记不清楚的话，我这里提供一个我自己的小技巧</p>
<ol>
<li>求最大化，右边比左边大，那 mid 就在右区间，而 mid 的左边 mid - 1 就是左区间，即[l, mid - 1]，[mid, r]；</li>
<li>求最小化，左边比右边小，那 mid 就在左区间，而 mid 的右边 mid + 1 就是右区间，即[l, mid]，[mid + 1, r]。</li>
<li>另外，如果只是单纯查找一个数，两个模板都可以用，或者使用最朴素的二分查找。</li>
</ol>
<h2 id="大数加减乘除"><a href="#大数加减乘除" class="headerlink" title="大数加减乘除"></a>大数加减乘除</h2><p>当运算数连 long long 都保存不了，就使用字符串或者整型数组来处理这类问题。</p>
<p>加法</p>
<pre><code class="c++">//123 在vector中为321 逆序存放
//&amp; 运算符可以加快传参速度
vector&lt;int&gt; add(vector&lt;int&gt; &amp;A, vector&lt;int&gt; &amp;B) &#123;
    //采用大数 + 小数的方式
    if (A.size() &lt; B.size()) return add(B, A);

    vector&lt;int&gt; ret;
    int carry = 0; //保存加法进位
    for (int i = 0; i &lt; A.size(); i++) &#123;
        //不断进行末位相加 结果是余数 进位不断前进
        carry += A[i];
        if (i &lt; B.size()) carry += B[i];
        ret.push_back(carry % 10);
        carry /= 10;
    &#125;
    //如果最后还有进位 就加进去
    if (carry) ret.push_back(carry);
    return ret;
&#125;
</code></pre>
<p>减法</p>
<pre><code class="c++">//与加法同理
vector&lt;int&gt; sub(vector&lt;int&gt; &amp;A, vector&lt;int&gt; &amp;B)
&#123;
    vector&lt;int&gt; ret;
    int carry = 0;
    for (int i = 0, t = 0; i &lt; A.size(); i++) &#123;
        carry = A[i] - carry;//如果有借位 就减掉
        if (i &lt; B.size()) carry -= B[i];
        ret.push_back((carry + 10) % 10);
        //每次借位只有0 或 1两种情况
        if (carry &lt; 0) t = 1; 
        else carry = 0;
    &#125;
    //消除前导0
    while (ret.size() &gt; 1 &amp;&amp; ret.back() == 0) ret.pop_back();
    return ret;
&#125;
</code></pre>
<p>乘法</p>
<ul>
<li><input disabled="" type="checkbox"> 大数和大数乘法</li>
</ul>
<pre><code class="c++">//首先是大数与一位数的乘法 再扩展到大数与大数的乘法
vector&lt;int&gt; mulSingle(vector&lt;int&gt; &amp;A, int b) &#123;
    vector&lt;int&gt; ret;
    int t = 0;
    
    for (int i = 0; i &lt; A.size() || t; i++) &#123;
        if (i &lt; A.size()) t += A[i] * b;
        ret.push_back(t % 10);
        t /= 10;
    &#125;
    //消除前导0 比如123 可能逆序存放为3210
    while (ret.size() &gt; 1 &amp;&amp; ret.back() == 0) ret.pop_back();

    return ret;
&#125;
</code></pre>
<p>除法</p>
<ul>
<li><input disabled="" type="checkbox"> 大数与大数除法</li>
</ul>
<pre><code class="c++">//A 被除数 b 除数 r 余数
//一般情况除数不会爆数据类型 使用普通除法就行
//极限情况的大数与大数除法 需要别的思路 还没有写好...
vector&lt;int&gt; div_1(vector&lt;int&gt; &amp;A, int b, int &amp;r) &#123;
    vector&lt;int&gt; ret;
    r = 0;
    for (int i = A.size() - 1; i &gt;= 0; i -- ) &#123;
        r = r * 10 + A[i];
        ret.push_back(r / b);
        r %= b;
    &#125;
    reverse(ret.begin(), ret.end());
    while (ret.size() &gt; 1 &amp;&amp; ret.back() == 0) ret.pop_back();
    return ret;
&#125;
</code></pre>
<h2 id="因数个数与因数之和"><a href="#因数个数与因数之和" class="headerlink" title="因数个数与因数之和"></a>因数个数与因数之和</h2><h3 id="因数个数"><a href="#因数个数" class="headerlink" title="因数个数"></a>因数个数</h3><pre><code class="c++">//因数个数
//原理: 每个质因子的最高次方+1的连乘
long long cal(int x) &#123;
    long long ans = 1, res = 0, temp = 0;
    Loop(i, 2, x) &#123;
        res = 0;
        while (x % i == 0) &#123;
            ++res;
            x /= i;
        &#125;
        ans *= (res + 1);
    &#125;
    return ans;
&#125;
</code></pre>
<h3 id="因数之和"><a href="#因数之和" class="headerlink" title="因数之和"></a>因数之和</h3><pre><code class="c++">//因数之和
//原理: 每个质因子从0次方加到它的最高次方，然后连乘。
//比如：求18 ，（2^0 + 2)*(3^0+3+3^2) = 3*13 = 39 
long long cal(int x) &#123;
    long long ans = 1, res = 0, temp = 0;
    Loop(i, 2, x) &#123;
        res = 1;
        while (x % i == 0) &#123;
            res *= i;
            x /= i;
        &#125;
        temp = (res * i - 1) / (i - 1);
        ans *= temp;
    &#125;
    return ans;
&#125;
</code></pre>
<h2 id="究极位运算用法收集"><a href="#究极位运算用法收集" class="headerlink" title="究极位运算用法收集"></a>究极位运算用法收集</h2></article><section class="jump-container is-flex is-justify-content-space-between my-6"><!-- em is empty placeholder--><a class="button is-default" href="/archives/3039932550/" title="Hexo博客多线部署 GitHub Gitee Coding 云服务器"><i class="iconfont icon-prev mr-2 has-text-grey"></i><span class="has-text-weight-semibold">上一页: Hexo博客多线部署 GitHub Gitee Coding 云服务器</span></a></section><article class="mt-6 comment-container"><script async src="https://utteranc.es/client.js" issue-term="pathname" theme="preferred-color-scheme"></script></article></div></div></main></main><footer class="is-flex is-flex-direction-column is-align-items-center is-flex-shrink-0 is-family-serif"><section class="sns-container"><!-- Github--><a title="github" target="_blank" rel="noopener nofollow" href="//github.com/insight-21"><i class="iconfont icon-github"></i></a><!-- Gitee--><a title="gitee" target="_blank" rel="noopener nofollow" href="//gitee.com/insight21"><i class="iconfont icon-gitee"></i></a><!-- Ins--><!-- RSS--><!-- 知乎--><!-- 领英--><!-- 脸书--></section><p><span>Copyright ©</span><span> insight 2021</span></p><div class="is-flex is-justify-content-center is-flex-wrap-wrap"><p>Powered by Hexo &verbar;&nbsp;</p><p class="is-flex is-justify-content-center"><a title="Hexo theme author" target="_blank" rel="noopener" href="//github.com/haojen">Theme by Haojen&nbsp;</a></p><div style="margin-top: 2px"><a class="github-button" title="github-button" target="_blank" rel="noopener" href="https://github.com/haojen/hexo-theme-Claudia" data-color-scheme="no-preference: light; light: light; dark: dark;" data-show-count="true"></a></div></div><div><span></span></div></footer><script async defer src="https://buttons.github.io/buttons.js"></script><script src="/js/post.js"></script></body></html>